|
|
Блог Ернара Шамбаева
|
Блог Ернара Шамбаева, посвященный казахской национальной игре - тогызкумалаку и компьютерной программе
|
|
Мастер тогызкумалака
Хорошая новость! Наконец-то появилась программа для смартфонов и планшетов (под управлением Android), играющая в древнюю казахскую национальную игру тогызкумалак на уровне лучших мастеров спорта.
Программа "Мастер тогызкумалака" будет интересной и полезной для всех любителей интеллектуальной игры, которой насчитывается около 4 тысяч лет. В приложении предусмотрены различные уровни сложности от начинающего до мастера.
Эта программа также станет незаменимым помощником для профессиональных спортсменов и тренеров, поскольку с ее помощью можно анализировать различные позиции и готовиться к турнирам.
Другие возможности:
- дебютная библиотека;
- база партий мастеров (около 1000 партий);
- тестирование знаний;
- зал славы;
- подробная статистика и динамика выступлений.
Ссылка на PlayMarket.
Лучшая двадцатка-2012
С 5 по 10 декабря 2012 года в Павлодарском Доме шахмат прошел ежегодный турнир по тогызкумалаку "Лучшая двадцатка", посвященный памяти Исатая Капаева, популяризатора игры тогызкумалак в Павлодарской области в советские годы.
Среди участников было семь международных мастеров (Серик Актаев, Максат Шотаев, Батырхан Абильбеков, Нурбек Кабиев, Диана Кенина, Айнур Жакапбаева, Гульжан Магауова) и пять мастеров спорта (Ернур Мерешев, Жанат Каймульдин, Алмаз Жаксылыков, Роза Раимбекова, Анастасия Фоос).
Компьютерная программа "Тогызкумалак" (создателями которой являются Ернар Шамбаев, Серик Актаев и Диана Кенина) во второй раз участвовала в этом турнире, причем если в прошлом году она соревновалась только с женщинами, то в этом году было принято решение запустить ее в оба турнира: и среди женщин, и среди мужчин.
Программа выступила успешно, победив в женском турнире и разделив 1-3 места в мужском (по дополнительным показателям она оказалась третьей). Особенно несладко пришлось международным мастерам, шестеро из них признали поражение в партиях против искусственного интеллекта.
Итоги "Лучшей двадцатки":
Мужской турнир
1. Нурбек Кабиев (мсмк) - 5 из 7
2. Жанат Каймульдин (мс) - 5 из 7
3. Программа "Тогызкумалак-2012" (мс) - 5 из 7
4-5. Серик Актаев (мсмк) - 3,5 из 7
Максат Шотаев (мсмк) - 3,5 из 7
6-8. Ернур Мерешев (мс) - 2 из 7
Алмаз Жаксылыков (мс) - 2 из 7
Батырхан Абильбеков (мсмк) - 2 из 7
Женский турнир
1. Программа "Тогызкумалак-2012" (мс) - 4 из 5
2. Роза Раимбекова (мс) - 4 из 5
3. Гульжан Магауова (мсмк) - 3 из 5
4. Диана Кенина (мсмк) - 2 из 5
5. Айнур Жакапбаева (мсмк) - 2 из 5
6. Анастасия Фоос (мс) - 0 из 5
Параллельно с "Лучшей двадцаткой" в Павлодаре проходило соревнование по тогызкумалаку на призы газеты "Сарыарка самалы" (до 9 лет, до 11 лет, до 13 лет, 13 лет и старше), собравшее свыше 200 участников и показавшее популярность казахской национальной игры в Павлодарской области.
Теги: тогызкумалак
Лучшая двадцатка
С 12 по 15 декабря в павлодарском Доме Шахмат прошел традиционный ежегодный турнир "Лучшая двадцатка", посвященный 20-летию Независимости Республики Казахстан, с участием сильнейших мастеров игры тогызкумалак. Особенностью данного турнира стало участие в нем программы "Тогызкумалак 2011" (впервые на официальном уровне). Дебют для компьютерной программы вышел удачным: она заняла третье место, победив трех мастеров спорта (С.Кусаинову, А.Такишеву и Г.Магауову) и уступив в двух встречах (упустив выигрыш с мастером спорта Р.Райымбековой и проиграв мастеру спорта международного класса Д.Кениной).
Перед началом соревнования высказывались сомнения в способности программы одержать хотя бы одну победу над квалифицированным игроком, но последующие результаты опровергли эти сомнения.
Многих удивила сила игры программы, особенно в самой сложной части игры - атсырау.
"Тогызкумалак 2011" была заявлена в женскую половину "Лучшей двадцатки", где не хватало одной участницы. Состав участниц был представительным: все квалифицированные и титулованные игроки (включая Диану Кенину - действующую чемпионку Азии и чемпионку Казахстана 2010-го года).
Я выполнял функции оператора и, хотя непосредственно не думал над партией, за эти несколько дней устал от нервного напряжения, словно сам участвовал в турнире. Оно и неудивительно, ведь я переживал за результаты своего детища.
Игры с участием программы происходили следующим образом: соперник (или точнее, соперница) делала ход, я передавал этот ход машине, дожидался ответа программы (запущенной на ноутбуке), а затем воспроизводил ее ход на доске. Подробнее о турнире (с примерами партий) в следующих записях блога.
Несмотря на неплохой результат, показанный программой (3 очка из 5 возможных, а могло бы быть и 4 из 5), я как ее разработчик не обольщаюсь, поскольку прекрасно понимаю, что программа еще очень далека от совершенства, ее игра далека от идеала, определенные позиции она понимает очень плохо (что и было продемонстрированно в 5-м туре в партии с Дианой). Могу сказать, что несмотря на простоту правил, тогызкумалак оказался крепким орешком в наше компьютерное время. До сегодняшнего дня в мире еще не существовало программы, способной переиграть мастера спорта. По богатству комбинаций, по неисчерпаемости игры, по глубине замыслов тогызкумалак сравним с шахматами.
В "Тогызкумалак 2011" было вложено много труда, времени и усилий, программа постоянно тестировалась, дорабатывалась, и в конце концов старания были вознаграждены.
На закрытии турнира я выразил благодарность Дастану Исатаевичу Капаеву за то, что он включил программу в "Лучшую двадцатку", а также Серику Актаеву и Диане Кениной (которые, как и я, являются создателями проекта) за их консультации и постоянную помощь. Они - настоящие энтузиасты игры и неслучайно стали мастерами спорта международного класса.
Можно с уверенностью сказать, что в истории игры тогызкумалак открыта новая страница. Главный итог турнира заключается в том, что уже существует электронный соперник, способный соперничать на равных с сильнейшими игроками и даже побеждать их. В истории этой древней и мудрой игры начинается новая эра - компьютерная.
Все материалы сайта можно использовать только с разрешения автора (Е. Шамбаева). При перепечатке активная ссылка на данный сайт обязательна X
Теги: капаев, тогызкумалак, турнир
Машина решает этюды
Около тридцати лет назад издательство "Жалын" выпустило книгу "Тогыз кумалак". Книгу написал Абилда Акшураев, и это была, пожалуй, первая серьезная попытка дать теоретическое описание основных принципов игры тогызкумалак. Помимо того, что в книге содержались созданные автором этюды и сыгранные в турнирах партии, она также включала в себя позиционные и тактические приемы, комбинации, была дана классификация дебютов. Кроме того, Акшураевым была проведена связь между игрой и математикой (подсчет ходов в концовке игры, влияние туздыка в той или иной лунке на количество оставшихся ходов, количество кумалаков, гарантированно набираемых даже при проигранном атсырау, и т.д.)
В главе "Этюды" приводится восемь этюдов, составленных автором книги, предлагается их решить, но решение в книге не приводится (по крайней мере, в издании 1983-го года, которое имеется у меня).
На программе "Тогызкумалак 2011" были протестированы все восемь этюдов, и она их решила. Задачи потребовали разное количество времени, поскольку для тех или иных задач потребовалась разная глубина перебора.
Для начала вам предлагается самим решить этюды, а потом сравнить свое решение с решением программы, которое будет приведено позже.
Условимся, что в приводимых диаграммах нижний ряд лунок принадлежит белым, верхний ряд - черным, правый казан - это казан белых, а левый казан - это казан черных.
Этюд 1. Ход белых, выигрыш.
Этюд 2. Ход белых, ничья.
Этюд 3. Ход белых, выигрыш.
Этюд 4. Ход белых, выигрыш.
Этюд 5. Ход белых, выигрыш.
Этюд 6. Ход белых, выигрыш.
Этюд 7. Ход белых, ничья.
Этюд 8. Ход белых, выигрыш.
Картинка взята с сайта http://www.etsy.com
Теги: тогызкумалак, этюды
Формат для записи партий тогызкумалак (Toguz Kumalak File Format Specification)
Вашему вниманию предоставляется разработанный Ернаром Шамбаевым формат TGK (Toguz Kumalak File Format Specification) для записи и хранения партий. Он частично основан на общепринятой форме записи партий, а также на формате записи шахматных партий PGN, ставший популярным благодаря удобству и наглядности. Формат удовлетворяет двум основным требованиям: 1) легок для записи и чтения людьми; 2) легок для разбора и генерации компьютерными программами. Будущим разработчикам программ для тогызкумалак рекомендуется придерживаться этой формы записи партий. В дальнейшем в блоге будет использоваться именно этот формат.
Каждая TGK-партия состоит из двух частей, разделенных пустой строкой: 1) метаданных, которые содержат информацию о партии в целом (кто играл белыми, кто играл черными, когда состоялась партия, где она состоялась, как завершилась и т.д.), и 2) собственно самой партии (в алгебраической нотации).
I. Метаданные
Первая часть партии заключает в себе список пар тегов, семь из которые обязательны.
Каждая пара тегов состоит из четырех последовательных лексем (лексема - это набор символов) в следующем порядке: левая квадратная скобка, словарная лексема, строковая лексема (взятая в кавычки) и правая квадратная скобка. Словарная лексема задает название тега (на английском языке), а строковая - его значение (на любом языке).
Пример: [White "Тогызкумалак 2011"].
Если строковая лексема неизвестна, то в качестве значения должен указываться знак вопроса.
В каждой партии обязательно должны присутствовать семь тегов: White, Black, Result, Date, Event, Round, Site. Порядок их в файле произволен.
1. White
Тег предназначен для указания имени игрока, играющего белыми.
Пример: [White "Кабиев"]
2. Black
Тег предназначен для указания имени игрока, играющего черными.
Пример: [Black "Отебаев"]
3. Result
Тег предназначен для указания результата партии. Должен принимать одно из четырех значений:
а) "1-0" (белые выиграли);
б) "0-1" (черные выиграли);
в) "1/2-1/2" (партия завершилась вничью);
г) "*" (игра продолжается или результат неизвестен).
4. Date
Тег предназначен для обозначения даты начала партии.
Пример: [Date "2011"] или [Date "2011.10.21"] (в формате "ГГГГ.ММ.ДД")
5. Event
Тег предназначен для обозначения турнира или матча.
Пример: [Event "Чемпионат Казахстана"]
6. Round
Тег предназначен для обозначения раунда или тура соревнования, в котором проводится партия.
Пример: [Round "9"]
7. Site
Тег предназначен для обозначения города или страны, в которой проводится партия.
Пример: [Site "Павлодар"]
II. Запись партии
Запись партии состоит из набора строк, каждая из которых содержит номер хода, ход белых и ход черных. Первое число задает номер хода, затем следует точка, за ней должен следовать пробел, затем ход белых, снова пробел и ход черных (если он был сделан).
Пример: 1. 76 98
Если ход привел к взятию туздыка, он должен обязательно сопровождаться символом "x".
Пример: 23. 93x 98x
Дополнительные (но необязательные) теги:
Count - для обозначения количества кумалаков в казанах в момент окончания партии
Пример: [Count "82-80"]
Comment - для кратких комментариев к партии
TimeControl - для описания контроля времени
WhiteElo и BlackElo - для обозначения рейтинга игроков
WhiteTitle и BlackTitle - для обозначения званий игроков
Пример партии, записанной в формате TGK:
[White "Кабиев"]
[Black "Отебаев"]
[Result "1-0"]
[Date "2011"]
[Event "Чемпионат Казахстана"]
[Round "9"]
[Site "Павлодар"]
[Comment "Выиграв эту партию, Кабиев стал новым чемпионом РК"]
1. 76 98
2. 66 87
3. 12 76
4. 25 35
5. 38 48
6. 42 24
7. 72 61
8. 34 17
9. 12 23
10. 89 12
11. 34 38
12. 47 48
13. 89 45
14. 78 23
15. 89 34
16. 62 12
17. 89 34
18. 78 45
19. 89 45
20. 67 23
21. 78 34
22. 45 23
23. 93x 98x
24. 35 12
25. 91 24
26. 12 85
27. 91 91
28. 13 61
29. 67 89
30. 23 92
31. 12 89
32. 91 78
33. 49 13
34. 91 24
35. 69 56
36. 56 12
37. 39 49
38. 47 71
39. 34 58
40. 69 45
41. 79 26
42. 95 13
43. 91
Все материалы сайта можно использовать только с разрешения автора (Е. Шамбаева). При перепечатке активная ссылка на данный сайт обязательна.
Теги: tgk, тогызкумалак, формат записи
Размышления о создании сильной программы (поиск истины)
Диана Кенина однажды сказала, что тогызкумалак для нее - это жизнь. Для меня тогызкумалак - это постоянный, непрекращающийся поиск истины, взлеты и падения, открытия и разочарования, своего рода научно-исследовательская работа.
Как говорил мой учитель математики, Темир Темиргалиевич Конурбаев, несмотря на то, что игра тогызкумалак имеет тысячелетнюю историю, она никогда не изучалась на научном уровне, с использованием математического аппарата.
Написать программу, умеющую играть в тогызкумалак, несложно. Это должен уметь делать любой студент любой специальности, имеющей отношение к информатике (надеюсь, что не за горами проведение чемпионата Казахстана среди компьютерных программ). Скорее всего, такая программа будет обыгрывать начинающих и слабых любителей, но споткнется в игре с первым же крепким игроком. Поэтому если вы привыкли доводить начатое дело до ума, то вам, без сомнений, захочется сделать программу, способную сражаться с сильнейшими игроками на равных и побеждать их. И вот здесь программист сталкивается с рядом сложностей. Одна из проблем - это недостаток литературы по теории игры тогызкумалак (дебютные монографии, например, вообще отсутствуют, очень мало книг по стратегии игры) и практически полное отсутствие литературы по программированию игр семейства манкала (поэтому приходится изобретать свои эвристики, затрачивая массу времени). Можно найти немного информации по программированию родственной игры - калаха (см. журнал "Наука и жизнь" за 1971-й год), но калах слишком прост в сравнении с тогызкумалаком. Как ни странно, в наше время проще написать сильную шахматную программу, потому что шахматному программированию около 50 лет и на эту тему существует масса статей, материалов и накопленного опыта.
В игре тогызкумалак присутствует уникальный элемент - это туздык. Честно говоря, трудно подыскать аналог туздыка в других логических играх. Любой программист, решающий описываемую задачу, вынужден дать туздыку количественную оценку, а с этим не так все просто. Если в шахматах давным-давно известна ценность каждой фигуры (пешка - одна единица, конь и слон - по три, ладья - пять единиц, ферзь - девять, хотя на самом деле эти величины имеют немного другие значения, но это не так важно), то как определить ценность туздыка? Ни один игрок (будь он опытный любитель либо чемпион мира) не сможет дать вам точный ответ на этот вопрос, а если и даст, то со множеством оговорок, допущений и исключений. Ценность туздыка зависит от того, где он расположен, в какой стадии он установлен, зависит от взаимного расположения туздыков и т.д. Туздык не имеет точного математического эквивалента, а при создании программ желательно иметь строгие числовые значения, а не расплывчатые рассуждения. Формализация человеческого мышления - нетривиальная задача и неслучайно написание программ, играющих в логические игры, относят к одному из разделов искусственного интеллекта.
Особую сложность составляет концовка игры (атсырау), где следует действовать исключительно точно. Этим не исчерпывается ряд сложностей, возникающих при создании действительно сильной программы.
В заключение статьи скажу, что игра тогызкумалак интересна тем, что нередко бывает сложно определить, где именно была допущена решающая ошибка (и это в некоторой степени роднит игру с го).
Все материалы сайта можно использовать только с разрешения автора (Е. Шамбаева). При перепечатке активная ссылка на данный сайт обязательна.
Теги: атсырау, компьютерная программа, тогызкумалак, туздык, формализация
Статистика по дебютам
Есть игры, исход которых заранее известен (крестики-нолики при точной игре с обеих сторон заканчиваются вничью, калах выигран за белых). С другими играми дело обстоит не так просто.
Рассмотрим начальную позицию игры тогызкумалак. В чью она пользу? Точный, математически обоснованный ответ на этот вопрос не сможет даст никто. Как уже было сказано в моей статье "Машина играет в тогызкумалак", дерево игры растет экспоненциально и для того, чтобы придти к терминальным позициям, у нас не хватит ни времени, ни компьютерных мощностей.
А что же говорит статистика?
Проведенный мной на основе 937 партий анализ (рассматривались партии, сыгранные в последнее время сильнейшими игроками в чемпионатах Казахстана, Азии, кубках РК, кубках Федераций РК и т.д.) показал, что у белых есть небольшое преимущество.
1. 21: 57 партий из 937 (6,08 %), Побед: 27, Поражений: 30, Ничьих: 0.
1. 32: 8 партий из 937 (0,85 %), Побед: 5, Поражений: 3, Ничьих: 0.
1. 43: 133 партии из 937 (14,19 %), Побед: 76, Поражений: 50, Ничьих: 7.
1. 54: 12 партий из 937 (1,28 %), Побед: 6, Поражений: 5, Ничьих: 1.
1. 65: 20 партий из 937 (2,13 %), Побед: 8, Поражений: 12, Ничьих: 0.
1. 76: 662 партии из 937 (70,65 %), Побед: 343, Поражений: 273, Ничьих: 46.
1. 87: 44 партии из 937 (4,70 %), Побед: 17, Поражений: 26, Ничьих: 1.
1. 98: 1 партия из 937 (0,11 %), Побед: 0, Поражений: 1, Ничьих: 0.
Подавляющее большинство партий (70 процентов) игралось дебютом 1. 76.
Наилучшие шансы у белых, когда они начинают партию ходами 1. 43 либо 1. 76.
Все материалы сайта можно использовать только с разрешения автора (Е. Шамбаева). При перепечатке активная ссылка на данный сайт обязательна.
Теги: дебюты, статистика, тогызкумалак
Мини-партии в тогызкумалаке (или "По следам дебютных катастроф")
В шахматах есть такое понятие - "кооперативный мат". Одна из сторон делает все возможное, чтобы как можно быстрее проиграть. Например, самая короткая шахматная партия может иметь такой вид: 1. g4 e5 2. f3 Фh4x.
А за сколько ходов можно проиграть в тогызкумалаке? Если очень постараться, то игра может закончиться уже на 6-м ходу.
Мной была написана небольшая программа, которая показала, что число максимально коротких партий в тогызкумалаке равняется 1391. Три самые короткие партии начинаются с хода 1. 54, девять партий начинается с хода 1. 87, девятнадцать партий - с хода 1. 76 и львиная доля партий (1360 или 97,77%) начинается с хода 1. 98. Парадоксально, ведь ход 1. 98 считается в дебюте одним из неудачнейших, однако при неверной игре со стороны черных он таит массу ловушек.
Ниже приведены партии-миниатюры на каждый дебют:
1. 54 11
2. 32 55x
3. 89 35
4. 78 47
5. 67 51
6. 46
1. 76 11
2. 65 77x
3. 89 13
4. 44 78
5. 33 82
6. 82
1. 87 11
2. 65 67
3. 78 13
4. 44 12
5. 33 67
6. 22
1. 98 11
2. 87 24
3. 76 13
4. 33 25
5. 55 34
6. 94
Полный список самых коротких партий можно посмотреть здесь:
http://www.toguzkumalak.idhost.kz/games.txt
Все материалы сайта можно использовать только с разрешения автора (Е. Шамбаева). При перепечатке активная ссылка на данный сайт обязательна.
Теги: дебюты, тогызкумалак
Машина играет в тогызкумалак (дерево игры)
"Машина играет в шахматы" - так называется книга авторов "Каиссы" (советской шахматной программы), из которой можно почерпнуть много полезного.
Нынче никого не удивишь программами, которые играют в интеллектуальные игры. Программы "думают" (анализируют текущую позицию), делают ходы (принимают решения) и способны сыграть целую партию, как и человек. И если в игре го их успехи пока не особо впечатляют (в силу специфики игры, но это особая история, заслуживающая отдельного блога), то в шахматах и шашках лучшие программы уже превосходят сильнейших гроссмейстеров.
Согласно теории игр (есть такой подраздел в математике), тогызкумалак (как и шахматы, как и го) относится к играм с полной информацией. Основные принципы написания программ для таких игр сформулировал еще в середине прошлого века Клод Шеннон, создатель теории информации.
Если вкратце, то программа для выбора хода (принятия решения) строит дерево игры, где корень - это исходная позиция, ветви - это возможные ходы, а листья - это позиции, возникшие в результате сделанных ходов (на самом деле, программа строит не дерево, а граф, но это несущественно).
У непосвященного человека может возникнуть вопрос, а возможно ли таким образом просчитать тогызкумалак до конца и на основе сделанного расчета играть идеально и безошибочно?
После первого хода белых может возникнуть 9 позиций, после ответного хода черных - 73 позиции. Программисты измеряют продолжительность партии в полуходах, поэтому будем придерживаться этой традиции. После трех полуходов имеем 613 возможных позиций, после четырех полуходов - 5 199.
Дерево игры растет экспоненциально, но пока не выглядит слишком страшным. Однако что будет дальше? После пяти полуходов - 43 184, после шести - 360 035, после семи - 3 003 052 (больше трех миллионов), после восьми - 25 166 174, после девяти - 210 521 787, после десяти - 1 766 804 407 (счет пошел уже на миллиарды), после одиннадцати - 14 811 651 049.
Таким образом, после 11 полуходов (то есть только после шести ходов белых и пяти ходов черных) возникает 15 миллиардов позиций. Это 15 миллиардов возможных партий! Если бы население всего Казахстана (16 миллионов человек), забросив все свои дела, расставили доски и воспроизвели все возможные партии после 11 полуходов, затрачивая на партию по полторы минуты, то это заняло бы почти сутки. И это всего лишь дебют, самое начало партии!
Теперь, думаю, понятно, почему игру тогызкумалак невозможно просчитать до конца и поэтому создание безошибочно играющей программы становится занятием проблематичным. Конечно, математики изобрели ряд механизмов отсечения части вариантов и сокращения дерева, но дерево игры по-прежнему остается огромным.
По моему мнению, тогызкумалак - это идеальная игра из семейства манкала. Очень удачно выбрано число лунок - 9. Если их число делать меньше (6, как в калахе), то запустив программу на несколько лет, можно получить окончательный результат игры при оптимальной игре обеих сторон. В том случае, если увеличить количество лунок, то игра приобретает затяжной характер и может продолжаться чрезмерно долго. Кстати, по этой же причине шахматы остаются в своем классическом варианте (8 на  , несмотря на многочисленные попытки модернизировать эту игру. Даже Капабланка в свое время предлагал добавить дополнительные фигуры и увеличить размер доски, но позже понял, что это заметно удлиняет партию и перестает делать шахматы столь интересными.
Все материалы сайта можно использовать только с разрешения автора (Е. Шамбаева). При перепечатке активная ссылка на данный сайт обязательна.
Теги: дерево игры, комбинаторика, логические игры, теория игр, тогызкумалак, шеннон
О блоге "Тогызкумалак"
Приветствую всех!
Меня зовут Ернар Шамбаев. Я являюсь одним из создателей компьютерной программы "Тогызкумалак". Работа над данным проектом - это моя попытка внести свой вклад в развитие культуры казахского народа. Моя цель - создать программу, которая будет сильнейшей не только среди остальных программ, но и среди людей.
С самого раннего детства меня увлекали логические и математические игры: шахматы, шашки, калах, отелло, го, а книга Якова Перельмана "Занимательная арифметика" была моей настольной книгой. В восьмом классе я перешел в математическую школу (гимназию), которая мне много дала. Оканчивая Павлодарский государственный университет, я узнал про казахскую национальную игру тогызкумалак и загорелся ею. Захотелось написать программу, которая бы играла в эту игру и побеждала человеческий разум. К тому времени у меня был не очень большой опыт написания приложений, поэтому программа получилась слабенькая, глубина перебора была небольшая, а оценочная функция примитивная. Я оставил тогызкумалак на долгое время, появились другие проекты и задачи, но наверное, я чувствовал, что рано или поздно я вернусь к этой удивительной игре.
Теги: искусственный интеллект, логические игры, математика, тогызкумалак
|
|
|
